package com.leetcode.www;

/**
 * Creared with IntelliJ IDEA.
 * Description:给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
 * User:yxd
 * Date:2022-03-16
 * Time:19:31
 */
public class DFS130 {
    public int[][] d = {{1,0},{-1,0},{0,1},{0,-1}};
    public void solve(char[][] board) {
        //只要右通路能出去就没有被包围,走不到边界就被包围了,我们可以从边界出发只要不是X就去搜索一下并标记出来,后面剩下的O全都是需要改成X的
        if(board == null)return;
        int row = board.length;
        int col = board[0].length;
        //第一行 最后一行
        for(int j = 0;j < col;j ++){
            if(board[0][j] == 'O'){
                DFS(board,row,col,0,j);
            }
            if(board[row - 1][j] == 'O'){
                DFS(board,row,col,row - 1,j);
            }
        }
        //第一列最后一列
        for(int i = 1;i < row - 1;i ++){
            if(board[i][0] == 'O'){
                DFS(board,row,col,i,0);
            }
            if(board[i][col - 1] == 'O'){
                DFS(board,row,col,i,col - 1);
            }
        }
        for(int i = 0;i < row;i ++){
            for(int j = 0;j < col;j ++){
                if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
                if(board[i][j] == 'A'){
                    board[i][j] = 'O';
                }
            }
        }


    }
    public void DFS(char[][] board,int row,int col,int curX,int curY){
        //当前要干什么,能进来搜索的都是没有被包围的O
        board[curX][curY] = 'A';
        for(int i = 0;i < 4;i ++){
            int newX = curX + d[i][0];
            int newY = curY + d[i][1];
            if(newX >= row || newX < 0
                    || newY >= col || newY < 0){//是否越界
                continue;
            }
            if(board[newX][newY] == 'O'){//连接的圈都需要标记出来
                DFS(board,row,col,newX,newY);
            }
        }
    }
}
